Madhur Tulsiani

Professor, Toyota Technological Institute at Chicago
Professor (part-time), Dept. of Computer Science, University of Chicago
Madhur Tulsiani
About

I am interested in Theoretical Computer Science, particularly in Complexity Theory. My research has been supported by NSF Career Award 1254044, NSF Award 1816372, and NSF Award 2326685.

Brief bio: I did my bachelor's in Computer Science at IIT Kanpur (2001–05) and a Ph.D. at UC Berkeley (2005–09) advised by the amazing Luca Trevisan. I was also a postdoc at the Institute for Advanced Study and Princeton University. Here's a CV if you want to know more.

Editorial
Theory of Computing
Recent PCs
STOC 2024 · SODA 2025 · CCC 2025 · FOCS 2026 · STOC 2027
Links
Theory@TTIC · Theory@UChicago · LucaFest
Teaching
Information and Coding Theory
2025 · 2022 · 2021 (with videos) · 2017 · 2014
Mathematical Toolkit
2025 · 2023 · 2021 (with videos) · 2019 · 2018 · 2016 · 2015 · 2013
Summer REUs
2014 · 2013
Students
Current
Alumni
  • June Wu U. Chicago, co-advised with Shmuel Weinberger. PhD 2025.
  • Tushant Mittal U. Chicago, co-advised with Janos Simon. PhD 2024. Now at Stanford.
  • Shashank Srivastava TTIC. PhD 2024. Now at IIT Bombay.
  • Goutham Rajendran U. Chicago, co-advised with Aaron Potechin. PhD 2022. Now at Google DeepMind.
  • Mrinalkanti Ghosh TTIC. PhD 2023. Now at IISc.
  • Fernando Granha Jeronimo U. Chicago, co-advised with Janos Simon. PhD 2021. Now at UIUC.
  • Dylan Quintana U. Chicago, co-advised with Sasha Razborov. PhD 2021. Now at CMU.
  • Pooya Hatami U. Chicago, co-advised with Sasha Razborov. PhD 2015. Now at Ohio State.
  • Pratik Worah U. Chicago, co-advised with Janos Simon. PhD 2013. Now at Google.
Papers
2026-2027
Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound
with Tushant Mittal, Shashank Srivastava, and Mary Wootters
Manuscript · arXiv
Sharp Phase Transition for Ellipsoid Fitting
with Sofia de la Cerda, Aaron Potechin, and Jeff Xu
Manuscript · arXiv
Optimal single-pass streaming lower bounds for approximating CSPs
with Noah Singer and Santhoshini Velusamy
FOCS 2026 · arXiv
2025
Sketching approximations and LP approximations for finite CSPs are related
with Noah Singer and Santhoshini Velusamy
Manuscript · arXiv
List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
with Shashank Srivastava
FOCS 2025 · arXiv · Talk
Invited to special issue on FOCS 2025.
Explicit Codes approaching Generalized Singleton Bound using Expanders
with Fernando Granha Jeronimo, Tushant Mittal and Shashank Srivastava
STOC 2025 · arXiv · Talk
Invited to special issue on STOC 2025.
Simple Norm Bounds for Polynomial Random Matrices via Decoupling
with June Wu
ITCS 2025 · arXiv
List Decodable Quantum LDPC Codes
with Thiago Bergamaschi, Fernando Granha Jeronimo, Tushant Mittal and Shashank Srivastava
QIP 2025 (poster) · arXiv
Ellipsoid fitting up to constant via empirical covariance estimation
with June Wu
SOSA 2025 · arXiv
2024
Efficient Certificates of Anti-Concentration Beyond Gaussians
with Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, and Aravindan Vijayaraghavan
FOCS 2024 · arXiv
2023
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates
with Fernando Granha Jeronimo and Shashank Srivastava
FOCS 2023 · arXiv · Talk
Concentration of polynomial random matrices via Efron-Stein inequalities
with Goutham Rajendran
SODA 2023 · arXiv · Talk
2022
Explicit Abelian Lifts and Quantum LDPC Codes
with Fernando Granha Jeronimo, Tushant Mittal, Pedro Paredes, and Ryan O'Donnell
ITCS 2022 · arXiv
Separating the NP-Hardness of the Grothendieck problem from the Little-Grothendieck problem
with Vijay Bhattiprolu and Euiwoong Lee
ITCS 2022 · Draft
2021
Sum-of-Squares Lower Bounds for Sparse Independent Set
with Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu
FOCS 2021 · arXiv
Near-linear Time Decoding of Ta-Shma's Codes via Splittable Regularity
with Fernando Granha Jeronimo and Shashank Srivastava
STOC 2021 · Draft · Talk
Explicit SoS lower bounds from high-dimensional expanders
with Irit Dinur, Yuval Filmus and Prahladh Harsha
ITCS 2021 · ECCC · arXiv · Talk
2020
Unique Decoding of Explicit ϵ-balanced Codes Near the Gilbert-Varshamov Bound
with Fernando Granha Jeronimo, Dylan Quintana and Shashank Srivastava
FOCS 2020 · arXiv · Talk
Invited to special issue on FOCS 2020.
List Decoding of Direct Sum Codes
with Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana and Shashank Srivastava
SODA 2020 · arXiv · Talk
2019
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
with Vedat Levi Alev and Fernando Granha Jeronimo
FOCS 2019 · arXiv
Approximating Operator Norms via Generalized Krivine Rounding
with Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami and Euiwoong Lee
SODA 2019 · arXiv
Inapproximability of Matrix p → q Norms
with Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami and Euiwoong Lee
SODA 2019 · ECCC · arXiv · Slides · Talk
2018
Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius
with Pooya Hatami
SODA 2018 · PDF
2017
Finding Pseudorandom Colorings of Pseudorandom Graphs
with Akash Kumar and Anand Louis
FSTTCS 2017
Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
with Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami and Euiwoong Lee
FOCS 2017 · ECCC · arXiv
From Weak to Strong LP Gaps for all CSPs
with Mrinalkanti Ghosh
CCC 2017 · ECCC · arXiv · Journal · Slides · Talk
Invited to special issue on CCC 2017.
2016
Proving Weak Approximability without Algorithms
with Ridwan Syed
APPROX 2016
An Arithmetic Analogue of Fox's Triangle Removal Argument
with Pooya Hatami and Sushant Sachdeva
Online Journal of Analytic Combinatorics · Journal · arXiv
2015
Algorithmic Regularity for Polynomials and Applications
with Arnab Bhattacharyya and Pooya Hatami
SODA 2015 · arXiv · PDF
2014
Optimal strong parallel repetition for projection games on low threshold rank graphs
with John Wright and Yuan Zhou
ICALP 2014
The Complexity of Somewhat Approximation Resistant Predicates
with Subhash Khot and Pratik Worah
ICALP 2014 · ECCC · Slides
Sampling-based proofs of almost-periodicity results and algorithmic applications
with Eli Ben-Sasson, Noga Ron-Zewi and Julia Wolf
ICALP 2014 · arXiv · ECCC
A Characterization of Strong Approximation Resistance
with Subhash Khot and Pratik Worah
STOC 2014 · arXiv · ECCC · Slides
Linear Programming Hierarchies Suffice for Directed Steiner Tree
with Zachary Friggstad, Young Kun Ko, Jochen Könemann, Anand Louis and Mohammad Shadravan
IPCO 2014
2013
LS+ Lower Bounds from Pairwise Independence
with Pratik Worah
CCC 2013 · ECCC
Towards An Optimal Query Efficient PCP?
with Subhash Khot and Muli Safra
ITCS 2013 · ECCC · Slides
2012
Reductions between Expansion Problems
with Prasad Raghavendra and David Steurer
CCC 2012 · Proceedings · arXiv · PDF · Slides
Graph Densification
with Moritz Hardt and Nikhil Srivastava
ITCS 2012 · Proceedings
2011
Quadratic Goldreich-Levin Theorems
with Julia Wolf
FOCS 2011 · Proceedings · arXiv · PDF
Invited to special issue on FOCS 2011.
Cuts in Cartesian Products of Graphs
with Sushant Sachdeva
Manuscript · arXiv · PDF
Algorithms and Hardness for Subspace Approximation
with Amit Deshpande and Nisheeth Vishnoi
SODA 2011 · arXiv · PDF
On LP-based Approximability for Strict CSPs
with Amit Kumar, Rajsekar Manokaran and Nisheeth Vishnoi
SODA 2011 · arXiv · PDF
2010
Improved Pseudorandom Generators for Depth 2 Circuits
with Anindya De, Omid Etesami and Luca Trevisan
RANDOM 2010 · Proceedings · ECCC · PDF · Slides
Time-Space Tradeoffs for Attacks against One-Way Functions and PRGs
with Anindya De and Luca Trevisan
CRYPTO 2010 · Proceedings · ECCC · PDF · Slides
SDP Gaps for 2-to-1 and other Label Cover Variants
with Venkatesan Guruswami, Subhash Khot, Preyas Popat, Ryan O'Donnell and Yi Wu
ICALP 2010 · Proceedings · PDF
2009
SDP Gaps from Pairwise Independence
with Siavosh Benabbas, Costis Georgiou and Avner Magen
APPROX 2009 · Proceedings · ECCC · PDF
Boosting, Regularity and Efficiently Simulating Every High-Entropy Distribution
with Luca Trevisan and Salil Vadhan
CCC 2009 · Proceedings · ECCC · PDF
CSP Gaps and Reductions in the Lasserre Hierarchy
—
STOC 2009 · Proceedings · ECCC · PDF
New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition
with Omer Reingold, Luca Trevisan and Salil Vadhan
Note · arXiv · PDF
2008
Dense Subsets of Pseudorandom Sets
with Omer Reingold, Luca Trevisan and Salil Vadhan
FOCS 2008 · Proceedings · ECCC · PDF · Slides
Unique Games on Expanding Constraint Graphs are Easy
with Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer and Nisheeth Vishnoi
STOC 2008 · Proceedings · PDF
Playing Random and Expanding Unique Games
with Alexandra Kolla
Manuscript · PDF
2007
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut
with Grant Schoenebeck and Luca Trevisan
STOC 2007 · Proceedings · ECCC · PDF · Slides (PPT)
A Linear Round Lower Bound for Lovasz Schrijver SDP Relaxations of Vertex Cover
with Grant Schoenebeck and Luca Trevisan
CCC 2007 · Proceedings · ECCC · PDF · Slides (PPT)
Surveys & Book Chapters
Survey talk on LP and SDP Hierarchies
Given at a Center for Intractability meeting · Slides
Lovasz-Schrijver Reformulation
Draft of article for Wiley Encyclopedia of Operations Research & Management Science · PDF
Convex Relaxations and Integrality Gaps
with Eden Chlamtac — article for Handbook on Semidefinite, Cone and Polynomial Optimization · PDF